// 封装双向链表类
function DoubleLinkedList () {
  // 封装内部类：节点类
  function Node (data) {
    this.data = data
    this.pre = null
    this.next = null
  }

  // 属性
  this.head = null
  this.tail = null
  this.length = 0

  // 常见的方法
  // 1.append方法
  DoubleLinkedList.prototype.append = data => {
    // 1. 根据data创建新节点
    const newNode = new Node(data)

    // 2.添加节点
    // 情况1：添加的是第一个节点
    if (this.length == 0) {
      this.head = newNode
      this.tail = newNode
    } else { // 情况2：添加的不是第一个节点
      newNode.pre = this.tail
      this.tail.next = newNode
      this.tail = newNode
    }

    // 3.length+1
    this.length += 1
  }

  // 2.将链表转变为字符串形式
  // 2.1 toString方法
  DoubleLinkedList.prototype.toString = () => {
    return this.backwardString()
  }
  // 2.2 forwardString方法
  DoubleLinkedList.prototype.forwardString = () => {
    // 1.定义变量
    let current = this.tail
    let resStr = ''

    // 2.依次向前遍历，获取每一个节点
    while (current) {
      resStr += current.data + '**'
      current = current.pre
    }
    return resStr
  }
  // 2.3 backwardString方法
  DoubleLinkedList.prototype.backwardString = () => {
    // 1.定义变量
    let current = this.head
    let resStr = ''

    // 2.依次向后遍历，获取每一个节点
    while (current) {
      resStr += current.data + '--'
      current = current.next
    }
    return resStr
  }

  // 3.insert方法
  DoubleLinkedList.prototype.insert = (position, data) => {
    // 1.越界判断
    if (position < 0 || position > this.length) return false

    // 2.根据data创建新的节点
    const newNode = new Node(data)

    // 3.插入新节点
    // 原链表为空
    // 情况1：插入的newNode是第一个节点 原链表为空
    if (this.length == 0) {
      this.head = newNode
      this.tail = newNode
    } else { // 原链表不为空
      // 情况2：position == 0
      if (position == 0) {
        this.head.pre = newNode
        newNode.next = this.head
        this.head = newNode
      } else if (position == this.length) { // 情况3：position == this.length
        this.tail.next = newNode
        newNode.pre = this.tail
        this.tail = newNode
      } else { // 情况4：0 < position < this.length
        let current = this.head
        let index = 0

        while (index++ < position) {
          current = current.next
        }

        // 修改pos位置前后节点变量的指向
        newNode.next = current
        newNode.pre = current.pre
        current.pre.next = newNode
        current.pre = newNode
      }
    }
    // 4.length+1
    this.length += 1
    return true // 返回true表示插入成功
  }

  // 4.get方法
  DoubleLinkedList.prototype.get = position => {
    // 1.越界判断
    if (position < 0 || position >= this.length) { // 获取元素时position不能等于length
      return null
    }

    // 2.获取元素
    let current = null
    let index = 0

    // this.length / 2 > position:从头开始遍历
    if ((this.length / 2) > position) {
      current = this.head
      while (index++ < position) {
        current = current.next
      }
      return current
    } else { // this.length / 2 =< position:从尾开始遍历
      current = this.tail
      index = this.length - 1
      while (index-- > position) {
        current = current.pre
      }
    }
    return current
  }

  // 5.indexOf方法
  DoubleLinkedList.prototype.indexOf = data => {
    if (data === undefined) return -1
    // 1.定义变量
    let current = this.head
    let index = 0

    // 2.遍历链表，查找与data相同的节点
    while (current) {
      if (current.data.toLowerCase() == data.toLowerCase()) {
        return index
      }
      current = current.next
      index++
    }
    return -1
  }

  // 6.update方法
  DoubleLinkedList.prototype.update = (position, newData) => {
    // 1.越界判断
    if (position < 0 || position >= this.length) return false

    // 2.寻找正确的节点
    let index = 0
    let current = this.head
    if (this.length / 2 > position) {
      while (index++ < position) {
        current = current.next
      }
    } else {
      current = this.tail
      index = this.length - 1
      while (index-- > position) {
        current = current.pre
      }
    }

    // 3.修改找到节点的data
    current.data = newData
    return true// 表示成功修改
  }

  // 7.removeAt方法
  DoubleLinkedList.prototype.removeAt = position => {
    // 1.越界判断
    if (position < 0 || position >= this.length) return null

    // 2.删除节点
    // 当链表中length == 1
    // 情况1：链表只有一个节点
    let current = this.head// 定义在最上面方便以下各种情况返回current.data
    if (this.length == 1) {
      this.head = null
      this.tail = null
    } else {
      // 情况2：删除第一个节点
      if (position == 0) {
        this.head.next.pre = null
        this.head = this.head.next
      } else if (position == this.length - 1) { // 情况3：删除最后一个节点
        current = this.tail // 该情况下返回被删除的最后一个节点
        this.tail.pre.next = null
        this.tail = this.tail.pre
      } else {
        let index = 0
        while (index++ < position) {
          current = current.next
        }
        current.pre.next = current.next
        current.next.pre = current.pre
      }
    }
    // 3.length -= 1
    this.length -= 1
    return current.data // 返回被删除节点的数据
  }

  /* --------------------其他方法------------------- */
  // 8.remove方法
  DoubleLinkedList.prototype.remove = data => {
    // 1.根据data获取下标值
    const index = this.indexOf(data)

    // 2.根据index删除对应位置的节点
    return this.removeAt(index)
  }

  // 9.isEmpty方法
  DoubleLinkedList.prototype.isEmpty = () => {
    return this.length == 0
  }
  // 10.size方法
  DoubleLinkedList.prototype.size = () => {
    return this.length
  }
  // 11.getHead方法：获取链表的第一个元素
  DoubleLinkedList.prototype.getHead = () => {
    return this.head
  }
  // 12.getTail方法：获取链表的最后一个元素
  DoubleLinkedList.prototype.getTail = () => {
    return this.tail
  }
  DoubleLinkedList.prototype.searchData = (data) => {
    const position = this.indexOf(data)
    return this.get(position)
  }
}
define([
], function () {
  'use strict'
  return DoubleLinkedList
})
